package leetcode.day_2020_12_07_12_14;

/**
 * 剑指 Offer 63. 股票的最大利润
 */
public class Offer_63 {
    public static void main(String[] args) {
        int[] prices = {7,1,5,3,6,4};
        System.out.println(maxProfit2(prices));
    }

    public static int maxProfit(int[] prices) {
        int n = prices.length;
        if (n==0) {
            return 0;
        }
        int[][] dp = new int[n][2];
        for(int i=0; i<n; i++){
            if(i-1 == -1) {
                dp[i][0] = 0;
                dp[i][1] = -prices[i];
                continue;
            }
            dp[i][0] = Math.max(dp[i-1][0], dp[i-1][1]+prices[i]);
            dp[i][1] = Math.max(dp[i-1][1], -prices[i]);
        }
        return dp[n-1][0];
    }

    public static int maxProfit2(int[] prices) {
        int n = prices.length;
        if (n==0) {
            return 0;
        }
        // base case, dp[i][0]=0, dp[i][1] = Integer.MIN_VALUE
        int dp_i_0 = 0, dp_i_1 = Integer.MIN_VALUE;
        for(int i=0; i<n; i++) {
            // dp[i][0] = Math.max(dp[i-1][0], dp[i-1][1]+prices[i]);
            dp_i_0 = Math.max(dp_i_0, dp_i_1 + prices[i]);
            // dp[i][1] = Math.max(dp[i-1][1], -prices[i]);
            dp_i_1 = Math.max(dp_i_1, -prices[i]);
        }
        return dp_i_0;
    }
}
